package com.czk.circleLinkedList;

/**
 * @Author:ChenZhangKun
 * @Date: 2020/6/18 22:35
 */
public class YosephCircleLinkedList {
    public static void main(String[] args) {
        CircleLinkedList circleLinkedList=new CircleLinkedList();
        circleLinkedList.addBoy(5);
        circleLinkedList.showList();
        circleLinkedList.countBoy(1,200,5);
    }
}

// 创建环形的单行链表
class CircleLinkedList{
    // 创建一个first节点
    private Boy first=new Boy(-1);
    // 添加小孩节点构建成环形的链表

    /**
     *
     * @param num 环形大小
     */
    public void addBoy(int num){
        // 对num进行数据校验
        if (num<1){
            System.out.println("number值不正确");
            return;
        }
        // 辅助构建环形链表
        Boy currentBoy=null;
        // 循环创建环形链表
        for (int i = 1; i <=num ; i++) {
            // 循环创建boy
            Boy boy=new Boy(i);
            if (i==1){
                // 第一个boy
                first=boy;
                // 设置第二个boy
                first.setBoy(first);
                // 当前的boy
                currentBoy=first;
            }else {
                // 设置当前的下一个节点
                currentBoy.setBoy(boy);
                // 连接第一个节点
                boy.setBoy(first);
                // 指向当前节点
                currentBoy=boy;
            }

        }
    }
    // 遍历链表
    public void showList(){
        // 链表为空的情况
        if (first==null){
            System.out.println("链表为空");
            return;
        }
        // first不能动，因此也需要一个辅助指针
        Boy currentBoy=first;
        while (true){
            System.out.printf("小孩的编号%d\n",currentBoy.getNo());
            if (currentBoy.getBoy()==first){
                return;
            }
            // 后移指针
            currentBoy=currentBoy.getBoy();
        }
    }
    // 根据用户的输入计算小孩出圈的熟顺序

    /**
     *
     * @param startNo 开始的编号
     * @param countNo 数数的数目
     * @param num 开始圈的人数
     */
    public void countBoy(int startNo,int countNo,int num){
        if(first==null||startNo<1||startNo>num){
            System.out.println("参数输入有误");
            return;
        }
        // 辅助指针
        Boy helper=first;
        // 初始化其为最后一个指针
        while (true){
            if (helper.getBoy()==first){
                break;
            }
            helper=helper.getBoy();
        }
        // 出列前先移动指针
        for (int i = 0; i <startNo-1 ; i++) {
            helper=helper.getBoy();
            first=first.getBoy();
        }
        while (true){
            if (helper==first){
                System.out.printf("最后留在圈中的小孩编号为%d\n",first.getNo());
                break;
            }
            for (int i = 0; i <countNo-1 ; i++) {
                first=first.getBoy();
                helper=helper.getBoy();
            }
            // 打印此时的first编号
            System.out.println(first.getNo());
            // first小孩节点出圈
            first=first.getBoy();
            // 移动帮助指针
            helper.setBoy(first);
        }
    }
}
// 创建一个boy类
class Boy{
    private int no;
    private Boy boy;

    public Boy(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getBoy() {
        return boy;
    }

    public void setBoy(Boy boy) {
        this.boy = boy;
    }
}
